package LeetCode;

/**
 * @author zhanghao
 * @create 2023-09-04 17:18
 *
 * 使用正则表达式匹配
 */
public class code8_RegularExpression {

    public boolean isMatch(String s, String p) {
        if(s == null || p == null){return false;}
        char [] str = s.toCharArray();
        char [] pattern = p.toCharArray();
        return isValid(str,pattern) && process(str,pattern,0,0);
    }

    //有效性检查，str中不能含有 . *
    public static boolean isValid(char[] str,char[] pattern){
        //在pattern中两个*不能靠在一起
        for(char cha : str){
            if(cha == '.' || cha == '*'){
                return false;
            }
        }

        for(int i = 0; i < pattern.length; i++){
            if(pattern[i] == '*' && (i == 0 || pattern[i - 1] == '*')){
                return false;
            }
        }
        return true;
    }

    //str[si...]能够被pattern[pi...]变出来
    public static boolean process(char[] str,char[] pattern,int si,int pi){
        //当我的si走到了str末尾的长度的位置
        if(si == str.length){
            //什么样的pattern可以匹配出 空的字符串来
            //情况1： pattern也结束了。空串是可以匹配出空串的
            if(pi == pattern.length){
                return true;
            }
            //情况2：str = ""; pattern = ""a*b*c*;
            //想办法将pattern变成0个a，0个b，0个c
            if(pi + 1 < pattern.length && pattern[pi+1] == '*'){
                //如果没有越界，并且i+1的位置 == *
                return process(str,pattern,si,pi+2);
            }
            return false;
        }

        //当pi位置走到终止的位置
        if(pi == pattern.length){
            return si == str.length;
        }

        //pi没有终止，si没有终止
        if(pi + 1 >= pattern.length || pattern[pi + 1] != '*'){
            //当前的位置相等
            return ((str[si] == pattern[pi]) || (pattern[pi] == '.'))
                    && process(str,pattern,si + 1,pi + 1);
        }
        //pi + 1 *
        if(pattern[pi] != '.' && str[si] != pattern[pi]){
            return process(str,pattern,si,pi + 2);
        }

        // pi + 1 位置是 * ，并且si和pi还能匹配上
        while (si < str.length && (str[si] == pattern[pi] || pattern[pi] == '.')){
            if(process(str,pattern,si + 1,pi + 2)){
                return true;
            }
            si++;
        }
        return false;
    }


}
